package com.c2b.algorithm.leetcode.base;

/**
 * <a href='https://leetcode.cn/problems/maximum-binary-tree-ii/'>最大二叉树 II(Maximum Binary Tree II)</a>
 * <p>最大树 定义：一棵树，并满足：其中每个节点的值都大于其子树中的任何其他值。</p>
 * <p>给你最大树的根节点 root 和一个整数 val 。</p>
 * <p>
 *     就像 <a href='https://leetcode.cn/problems/maximum-binary-tree/'>之前的问题</a> 那样，给定的树是利用 Construct(a) 例程从列表 a（root = Construct(a)）递归地构建的：
 *     <ul>
 *         <li>如果 a 为空，返回 null 。</li>
 *         <li>否则，令 a[i] 作为 a 的最大元素。创建一个值为 a[i] 的根节点 root 。</li>
 *         <li>root 的左子树将被构建为 Construct([a[0], a[1], ..., a[i - 1]]) 。</li>
 *         <li>root 的右子树将被构建为 Construct([a[i + 1], a[i + 2], ..., a[a.length - 1]]) 。</li>
 *         <li>返回 root 。</li>
 *     </ul>
 *     请注意，题目没有直接给出 a ，只是给出一个根节点 root = Construct(a) 。
 * </p>
 * <p>假设 b 是 a 的副本，<b>并在末尾附加值 val</b>。题目数据保证 b 中的值互不相同。</p>
 * <p>返回 Construct(b) 。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root = [4,1,3,null,null,2], val = 5
 *                          4
 *                        /  \
 *                       1    3
 *                           /
 *                          2
 *      输出：[5,4,null,1,3,null,null,2]
 *                          5
 *                         /
 *                        4
 *                      /  \
 *                     1    3
 *                         /
 *                        2
 *      解释：a = [1,4,2,3], b = [1,4,2,3,5]
 *
 * 示例 2：
 *      输入：root = [5,2,4,null,1], val = 3
 *                          5
 *                        /  \
 *                       2    4
 *                        \
 *                         1
 *      输出：[5,2,4,null,1,null,3]
 *                          5
 *                        /  \
 *                       2    4
 *                        \    \
 *                         1    3
 *      解释：a = [2,1,5,4], b = [2,1,5,4,3]
 *
 * 示例 3：
 *      输入：root = [5,2,3,null,1], val = 4
 *                          5
 *                        /  \
 *                       2    3
 *                        \
 *                         1
 *      输出：[5,2,4,null,1,3]
 *                          5
 *                        /   \
 *                       2     4
 *                        \   /
 *                         1 3
 *      解释：a = [2,1,5,3], b = [2,1,5,3,4]
 * </pre>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>树中节点数目在范围 [1, 100] 内</li>
 *     <li>1 <= Node.val <= 100</li>
 *     <li>树中的所有值 互不相同</li>
 *     <li>1 <= val <= 100</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/11/22 11:04
 */
public class LC0998MaximumBinaryTree_II_M {
    static class Solution {
        public TreeNode insertIntoMaxTree(TreeNode currNode, int val) {
            // root.val 为所有节点中的最大值。
            // 如果树中所有节点值添加到数组中。root.val为数组中的最大值，对应下标左侧所有值构成左子树，对应下标右侧所有值构成右子树
            /*
                添加 val 到数组的末尾，有两种情况：
                    // 1.val比最大值大。val对应的节点作为根节点；之前的树作为当前节点的左子树
                    // 2.val比最大值小。将当前值插入到右树中
                    // 3.重复1，2
             */
            if (currNode == null) {
                return new TreeNode(val);
            }
            if (val > currNode.val) {
                TreeNode node = new TreeNode(val);
                node.left = currNode;
                return node;
            }
            currNode.right = insertIntoMaxTree(currNode.right, val);
            return currNode;
        }
    }

    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(4);
        root1.left = new TreeNode(1);
        root1.right = new TreeNode(3);
        root1.right.left = new TreeNode(2);

        TreeNode root2 = new TreeNode(5);
        root2.left = new TreeNode(2);
        root2.right = new TreeNode(4);
        root2.left.right = new TreeNode(1);


        TreeNode root3 = new TreeNode(5);
        root3.left = new TreeNode(2);
        root3.right = new TreeNode(3);
        root3.left.right = new TreeNode(1);

        Solution solution = new Solution();
        TreeNode.printTree(solution.insertIntoMaxTree(root1, 5));
        TreeNode.printTree(solution.insertIntoMaxTree(root2, 3));
        TreeNode.printTree(solution.insertIntoMaxTree(root3, 4));
    }
}
